package 热题100;

import java.util.Arrays;

public class 归并排序 {

    public static void main(String[] args) {
        int[] arr = {4,3,2,1};
        sort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }


    public static void sort(int[]arr ,int left ,int right){
        int mid = (left + right) >> 1;
        if (left < right){
            sort(arr,left,mid);
            sort(arr,mid + 1,right);
        }
        int[] tem = new int[arr.length];
        sortHelp(arr,left,mid,right,tem);
    }

    private static void sortHelp(int[] arr, int left, int mid, int right, int[] tem) {
        int l = left;
        int r = mid + 1;
        int index = left;

        while (l <= mid && r <= right){
            if (arr[l] < arr[r]){
                tem[index] = arr[l];
                l++;
            }else {
                tem[index] = arr[r];
                r++;
            }
            index++;
        }

        while (l <= mid){
            tem[index] = arr[l];
            l++;
            index++;
        }

        while (r <= right){
            tem[index] = arr[r];
            index++;
            r++;
        }

        int temIndex = left;
        while (temIndex <= right){
            arr[temIndex] = tem[temIndex];
            temIndex++;
        }
    }

}
